package com.java.comprehensive.arithmetic.leecode.medium;

import cn.hutool.core.util.ArrayUtil;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: 窦绍飞
 * @Date: 2022/8/2
 */
public class LeetCode_77 {

	List<List<Integer>> result = new ArrayList<>();
	List<Integer> temp = new ArrayList<>();

	public List<List<Integer>> combine(int n, int k) {
		if (n < 1) {
			return result;
		}
		backtracking(n, k, 0);
		return result;
	}

	public void backtracking(Integer n, Integer k, Integer startIndex) {
		if (k == temp.size()) {
			result.add(new ArrayList<>(temp));
			return;
		}
		//k是需要组合的个数 temp。size 是已经组合的个数
		//剪枝条件n+1 是因为 下标从0开始 0<n 比方0-3 其实有四个数字 应该 用 N+1之后的数字来减去还差几个满足case条件（k-temp.size）
		//剪枝的条件就是 去掉循环中无法组合的数字不进行多余循环
		for (int i = startIndex; i < n + 1 - (k - temp.size()); i++) {
			temp.add(i + 1);
			backtracking(n, k, i + 1);
			temp.remove(temp.size() - 1);
		}
	}

	public static void main(String[] args) {
		LeetCode_77 leetCode_77 = new LeetCode_77();
		int n = 4;
		int k = 2;
		List<List<Integer>> combine = leetCode_77.combine(n, k);
		System.out.println(ArrayUtil.toString(combine));
	}
}
